\documentclass[12pt,letterpaper]{report}
\usepackage{fancyhdr}
\fancypagestyle{preliminary} {%
\fancyhf{}
\pagenumbering{roman}
\fancyfoot[C]{~~~~~~~~\thepage}
\setlength{\footskip}{.85in}
%\addtolength{\footskip}{.5in}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt} }
\fancypagestyle{plain} {%
\fancyhf{}
\fancyfoot[C]{~~~~~~~~\thepage}
\setlength{\footskip}{.85in}
%\addtolength{\footskip}{.5in}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt} }
\pagestyle{preliminary}
\usepackage{t1enc}
\usepackage[latin1]{inputenc}
\usepackage[english]{babel}
%\usepackage{algorithm}
%\usepackage[noend]{algorithmic}
%\RequirePackage{amsmath}
%\RequirePackage{amsthm}
\usepackage{latexsym}
\usepackage{graphicx, epsfig}
\usepackage{amsmath, amsthm, amsfonts}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
%\usepackage{fullpage}
%\usepackage{subfigure}
\usepackage{subfig}
%\addtolength{\textwidth}{1.2in} \addtolength{\hoffset}{-0.6in}
%\addtolength{\textheight}{1.5in} \addtolength{\voffset}{-0.7in}
%\renewcommand{\baselinestretch}{1.3}
\topmargin0in
\oddsidemargin.4in
\textwidth5.8in
\textheight8.3in
\setlength{\parskip}{12pt}
\setlength{\parindent}{0pt}
\linespread{1.6}
%\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{definition}{Definition}[chapter]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{property}[theorem]{Property}


%\documentclass[12pt]{report}
%\usepackage{latexsym}
%\usepackage{graphicx, epsfig}
%\usepackage{amsmath, amsthm, amsfonts}
%\usepackage{algorithm}
%\usepackage[noend]{algorithmic}
%\usepackage{fullpage}
%\usepackage{subfigure}
\usepackage{subfig}
%\addtolength{\textwidth}{1.2in} \addtolength{\hoffset}{-0.6in}
%\addtolength{\textheight}{1.5in} \addtolength{\voffset}{-0.7in}
%\renewcommand{\baselinestretch}{1.3}

%\newtheorem{theorem}{Theorem}
%\newtheorem{definition}{Definition}[chapter]
%\newtheorem{corollary}{Corollary}
%\newtheorem{lemma}{Lemma}
%\newtheorem{claim}{Claim}

\newcommand{\BfPara}[1]{\noindent{\bf #1}.}
\newenvironment{junk}[1]{}

\title{Decentralized Network Design}
\author{Laura J. Poplawski}

\begin{document}
\newenvironment{LabeledProof}[1]{\noindent{\it Proof of #1: }}{\qed}
%\date{}
%\maketitle

\newcommand{\eps}{\varepsilon}
\newcommand{\PPAD}{${\bf{PPAD}}$}
\newcommand{\TFNP}{${\bf{TFNP}}$}
\newcommand{\FP}{${\bf{FP}}$}
\newcommand{\NP}{${\bf{NP}}$}
\newcommand{\reduce}{$\leq_P$}

\newcommand{\leqprefer}{\preceq}
\newcommand{\geqprefer}{\succeq}
\newcommand{\ltprefer}{\prec}
\newcommand{\gtprefer}{\succ}
\newcommand{\eqprefer}{=}

\newcommand{\pInstance}{$\textbf{P}$}
\newcommand{\bInstance}{$\textbf{B}$}
\newcommand{\mInstance}{$\textbf{M}$}
\newcommand{\ib}{i}
\newcommand{\jb}{j}

% preference game reductions
\newcommand{\inedges}{\mbox{in}}
\newcommand{\outedges}{\mbox{out}}


\newcommand{\eol}{{\sc{End of the Line}}}
\newcommand{\prefGame}{{\sc{Preference Game}}}
\newcommand{\approxPrefGame}{{\sc{$\epsilon$-Approximate Preference Game}}}
\newcommand{\constDegreePrefGame}[1]{{\sc{Degree $#1$ Preference Game}}}
\newcommand{\threeDBrouwer}{{\sc{3-D Brouwer}}}
\newcommand{\brouwer}{{\sc{Brouwer}}}
\newcommand{\pe}{{\sc{Personalized Equilibrium}}}
\newcommand{\constPlayersPe}[1]{{\sc{$#1$-Personalized Equilibrium}}}
\newcommand{\constDegreePe}[1]{{\sc{$#1$-Graphical Personalized Equilibrium}}}
\newcommand{\approxPe}{{\sc{$\epsilon$-Approximate Personalized Equilibrium}}}
\newcommand{\hypergraph}{{\sc{Fractional Hypergraph Matching}}}
\newcommand{\fspp}{{\sc{FSPP}}}
\newcommand{\fbbc}{{\sc{FBBC}}}
\newcommand{\stfl}{{\sc{STFL}}}

\newcommand{\budgetnoargs}{b}
\newcommand{\budget}[1]{b(#1)}
\newcommand{\length}[3]{\ell_{#1}(#2,#3)}
\newcommand{\lengthonearg}[1]{\ell_{#1}}
\newcommand{\cost}[2]{c(#1,#2)}
\newcommand{\costnoargs}{c}
\newcommand{\dist}[1]{\mbox{cost}(#1)}
\newcommand{\distnoargs}{\mbox{cost}}
\newcommand{\pref}[2]{w(#1,#2)}
\newcommand{\affinity}[2]{w(#1,#2)}
\newcommand{\prefnoargs}{w}
\newcommand{\dest}{d}


\thispagestyle{empty}

      \begin {center}
         \vfill
         \textsc{\large Northeastern University} \\
         \normalsize Boston, MA \\
         \vskip 48pt plus0pt minus18pt
         Decentralized Network Design \\
         \vskip 48pt plus0pt minus18pt
         \normalsize A thesis submitted in partial satisfaction \\
         of the requirements for the degree Doctor of Philosophy \\
              in Computer Science
         \vskip 24pt plus0pt minus6pt
         by \\
         \vskip 24pt plus0pt minus6pt
         Laura Jane Poplawski \\
         \vfill
         {\normalsize 2009}
      \end {center}

\clearpage

\pagenumbering{roman}

\tableofcontents

\clearpage

\listoffigures
\clearpage

      \begin {center}
         \textsc{\large acknowledgments} \\
      \end{center}
      \vskip 24pt plus0pt minus18pt
      Chapter \ref{sec:bbc} is based on: \\ \\
      N. Laoutaris, L. Poplawski, R. Rajaraman, R. Sundaram and S.-H. Teng.
      Bounded Budget Connection (BBC) Games or How to Make Friends and Influence People, on a Budget.
      \emph{PODC}, 2008 and arXiv:0806.1727v1 [cs.GT], 2008.
      \vskip 12pt plus0pt minus18pt
      Chapter \ref{sec:fractionalGames} is based on: \\ \\
      S. Kintali, L. Poplawski, R. Rajaraman, R. Sundaram and S.-H. Teng. 
      Reducibility Among Fractional Stability Problems.
      \emph{ECCC}, 2009 and \emph{FOCS}, 2009.
      \vskip 12pt plus0pt minus18pt
      Chapter \ref{sec:personalized} is joint work with R. Rajaraman, R. Sundaram, and S.-H. Teng and is partially based on: \\ \\
      S. Kintali, L. Poplawski, R. Rajaraman, R. Sundaram and S.-H. Teng. 
      Reducibility Among Fractional Stability Problems.
      \emph{ECCC}, 2009 and \emph{FOCS}, 2009.
      \vskip 12pt plus0pt minus18pt
      Chapter \ref{sec:facilityLocation} is based on joint work with Rajmohan Rajaraman.

\clearpage

      \begin {center}
         \textsc{\large abstract of the thesis} \\
         \vskip 24pt plus0pt minus18pt
         Decentralized Network Design \\
         \vskip 12pt plus0pt minus18pt
         by \\
         Laura Jane Poplawski \\
         \vskip 12pt plus0pt minus18pt
         PhD in Computer Science \\
         Northeastern University, 2009 \\
         \vskip 24pt plus0pt minus18pt
      \end {center}

Most overlay networks are designed by a centralized algorithm, which takes the participating nodes and returns a set of edges connecting the nodes. We study the possible results of decentralizing overlay network design. What would happen if the individual nodes in the network were asked to choose their own connections? We use techniques from game theory to consider issues such as the stability and fairness of the resulting networks. We define and study several games, all with relevant applications. 

First, we study variants of the Bounded Budget Connection (BBC) game, in which each node has some budget to spend on outgoing links and wants to minimize its distance to other nodes in the network. We show that this game does not always guarantee a stable network. However, if we allow nodes to fractionally purchase links, as in the fractional BBC game, then a stable solution always exists, although it may be hard to find. We give existence and hardness results for fractional BBC games, as well as for two other fractional games: the fractional Shortest Paths Problem (SPP) game, which may capture the routing behavior of Autonomous Systems using the Border Gateway Protocol, and the preference game, a very simple fractional game which is a specialization of both fractional BBC and fractional SPP games. We study a new equilibrium solution concept for matrix games, called personalized equilibria, which generalizes all of these fractional games as well as modeling real-world scenarios. Finally, we study the interaction between a centralized algorithm placing resources in the network and nodes choosing their own edges or routes -- a variant of multicommodity facility location in which clients pay the cost of a minimum Steiner tree connecting them to commodities of interest. 

\clearpage

\pagenumbering{arabic}

\chapter{Introduction}
\input{introduction} 

\chapter{Bounded Budget Connection Games} \label{sec:bbc}
\input{bbc_chapter}

\chapter{Fractional Games} \label{sec:fractionalGames}
\input{fractional_chapter}

\chapter{Personalized Equilibria} \label{sec:personalized}
\input{personalized_chapter}

\chapter{Centralized Facility Location on a Selfishly Designed Network} \label{sec:facilityLocation}
\input{stfl_chapter}

\chapter{Conclusion} \label{sec:conclusion}
\input{conclusion}

\bibliographystyle{alpha}
\bibliography{bibliography}

\end{document}